package com.LeetCode.Graph;

import org.junit.Test;

import java.util.*;

/**
 * 火星词典
 */
public class NewCharOrder {
    public String alienOrder(String[] words) {
        //构建一张图
        Map<Character, Set<Character>> map = new HashMap<>();
        for(int i = 0; i<words.length - 1; i++){

            int len = Math.max(words[i].length(), words[i + 1].length());

            for(int j = 0; j<len; j++){

                if (j >= words[i].length()) break;
                if(j >= words[i+1].length()) return "";

                if(words[i].charAt(j) == words[i+1].charAt(j))
                    continue;


                Set<Character> set = map.getOrDefault(words[i].charAt(j),new HashSet<>());
                set.add(words[i+1].charAt(j));//标记 word[i].charAt(j) 的字典序在 word[i+1].charAt(j)之前
                map.put(words[i].charAt(j),set);
                //两个相邻的词只能判断出一对字典关系
                break;
            }
        }

        //拓扑排序
        int[] indegrees = new int[26];
        //默认是没有出现过的
        Arrays.fill(indegrees,-1);

        for(String str : words){
            char[] chars = str.toCharArray();
            for(char c : chars){
                //出现过就标记为1
                indegrees[c-'a'] = 0;
            }
        }

        for(char key : map.keySet()){
            for(char val : map.get(key)){
                indegrees[val - 'a']++;
            }
        }

        StringBuilder strb = new StringBuilder();

        //存放入度为0的节点
        Queue<Character> queue = new LinkedList<>();

        int count = 0;
        for(int i = 0; i<26; i++){
            if(indegrees[i]!=-1) count++;
            if(indegrees[i] == 0){
                queue.offer((char)('a' + i));
            }
        }

        while(!queue.isEmpty()){
            Character cur = queue.poll();
            strb.append(cur);
            if(map.containsKey(cur)){
                Set<Character> set = map.get(cur);
                for(Character c : set){
                    indegrees[c - 'a'] --;
                    if(indegrees[c - 'a'] == 0) queue.add(c);
                }
            }
        }
        return strb.length() != count ? "" :strb.toString();
    }

    @Test
    public void test(){
        String[] words ={"abc","ab"};
        System.out.println(alienOrder(words));
    }
}
